package com.practice.niuke.new_direct_practice.class32;

/**
 * （最大的消消乐点数）
 * Given several boxes with different colors represented by different positive numbers.
 * You may experience several rounds to remove boxes until there is no box left. Each time
 * you can choose some continuous boxes with the same color (composed of k boxes, k >= 1),
 * remove them and get k*k points.
 * Find the maximum points you can get.
 * Example 1:
 * Input:
 * [1, 3, 2, 2, 2, 3, 4, 3, 1]
 * Output:
 * 23
 * Explanation:
 * [1, 3, 2, 2, 2, 3, 4, 3, 1]
 * ----> [1, 3, 3, 4, 3, 1] (3*3=9 points)
 * ----> [1, 3, 3, 3, 1] (1*1=1 points)
 * ----> [1, 1] (3*3=9 points)
 * ----> [] (2*2=4 points)
 */
public class Code01_RemoveBoxes {

	public int removeBoxes(int[] boxes) {
		int N = boxes.length;
		int[][][] dp = new int[N][N][N];
		return process(boxes, 0, N - 1, 0, dp);
	}

	public static int process(int[] boxes, int i, int j, int k, int[][][] dp) {
		if (i > j) {
			return 0;
		}
		if (dp[i][j][k] != 0) {
			return dp[i][j][k];
		}
		if (i == j) {
			dp[i][j][k] = (k + 1) * (k + 1);
			return dp[i][j][k];
		}
		while (i < j && boxes[i] == boxes[i + 1]) {
			i++;
			k++;
		}
		int ans = (k + 1) * (k + 1) + process(boxes, i + 1, j, 0, dp);
		for (int m = i + 1; m <= j; m++) {
			if (boxes[i] == boxes[m]) {
				ans = Math.max(ans, process(boxes, i + 1, m - 1, 0, dp) + process(boxes, m, j, k + 1, dp));
			}
		}
		dp[i][j][k] = ans;
		return ans;
	}

}
